
class BinaryHeapTree<T extends Comparable<T>> extends BinaryHeap<T> {
    //Members
    private Node<T> m_root;
    int m_size;
    //Constructor, Start with an empty node (Node is needed, so that a tree can b empty)
    BinaryHeapTree() { super(); m_root = null; m_size = 0; }
    //Public methods
    //Returns if the heap is empty or not
    @Override
    public boolean isEmpty() { return m_size <= 0; }  
    //Returns the size, number of elements (=maxIndex+1), of the heap
    @Override
    public int size() { return m_size; }
    //Just returns the top (largest value) without modifying the heap 
    @Override
    public T getTop() { return m_root.value; } 
    //Just returns the value at index i without modifying the heap
    @Override
    public T get(int i) { return get(i, 0, m_root); }
    //Just puts this value at index i, and returns the old value at index i, 
    //without modifying the rest of the heap 
    @Override
    public T set(int i, T val) { return set(i, 0, m_root, val); }
    //Add element as last and then move up as long as it is bigger than its parent
    @Override
    public void addElement(T v) { 
        if (isEmpty()) { 
            m_root = new Node(v);
        } else {
            addElement(m_size, 0, m_root, v);  //m_size=nextFilledIndex
        } 
        m_size++; //Increment size AFTER we added the new element
    }
    //Remove top, heapify and then return old top
    @Override
    public T removeTop() {                      
        if (m_root == null) return null; //If tree is null, top is null  
        T top;
        if (m_root.isLeaf()) {
            top = m_root.value;
            m_root = null;
            m_size--;  
        } else {
            top = removeTop(0, m_root); //m_size-- is done inside!!!
        }
        return top; 
    }
    //Removes the element with highest index 
    public T removeLast() {
        if (m_root == null) return null; //If tree is null, last value is null
        T val;
        if (m_root.isLeaf()) {
            val = m_root.value;
            m_root = null;
        } else {
            val = removeBranch(m_size - 1, 0, m_root);
        }
        m_size--;  //Decrement size AFTER we deleted the top element
        return val;
    }
                
    //This is private! Users should use addElement(T) instead
    private void addElement(int wantIndex, int currentIndex, Node<T> N, T val) {
        if (N == null) System.out.println("ERROR, N should not be null here!");
        if (val.compareTo(N.value) > 0) {
            T newValue = N.value;
            N.value = val; 
            val = newValue;  //new value to move down
        }
        if (wantIndex == leftChild(currentIndex)) {
            if (N.left != null) System.out.println("ERROR: N.left should be null here!");
            N.left = new Node(val);
        } else if (wantIndex == rightChild(currentIndex)) {
            if (N.right != null) System.out.println("ERROR: N.right should be null here!");
            N.right = new Node(val);
        } else {
            if ((N.left == null)||(N.right == null)) System.out.println("ERROR: no child should b null");
            int leftIndex = leftChild(currentIndex);
            if (leftLeadsToIndex(wantIndex, currentIndex)) { addElement(wantIndex, leftIndex, N.left, val); 
            } else { addElement(wantIndex, rightChild(currentIndex), N.right, val); }
        }
    }
    //This is private! Users should use removeTop() instead
    private T removeTop(int currentIndex, Node<T> branch) {    //Cannot be a leaf
        T topValue = branch.value;
        branch.value = removeLast();   //m_size-- is done inside!!!
        //Now move down the new top value until it is bigger than all its children
        swapDownUntilBigParent(branch);
        return topValue; 
    }
    
    private void swapDownUntilBigParent(Node<T> N) {
        if (!N.isLeaf()) {            //if it is, we don't do anything
            if (!N.isBigParent()) {   //if it is, we don't do anything
                T temp = N.value;
                if (N.leftIsLarger()) {
                    N.value = N.left.value;
                    N.left.value = temp;
                    swapDownUntilBigParent(N.left);
                } else {
                    N.value = N.right.value;
                    N.right.value = temp;
                    swapDownUntilBigParent(N.right);
                }
            }
        }
    }
    
    //This is private! Users should use  set(int, T)  instead
    private T set(int wantIndex, int currentIndex, Node<T> branch, T val) {
        if (branch == null) return null; //If this branch is null we did not find it
        if (wantIndex == currentIndex) {
            T oldVal = branch.value;
            branch.value = val;
            return oldVal;
        }
        if (leftLeadsToIndex(wantIndex, currentIndex)) return set(wantIndex, leftChild(currentIndex), branch.left, val);
        return set(wantIndex, rightChild(currentIndex), branch.right, val);
    } 
    //This is private! Users should use  get(int)  instead
    private T get(int wantIndex, int currentIndex, Node<T> branch) {
        if (branch == null) return null; //If this branch is null we did not find it
        if (wantIndex == currentIndex) return branch.value;
        if (leftLeadsToIndex(wantIndex, currentIndex)) return get(wantIndex, leftChild(currentIndex), branch.left);
        return get(wantIndex, rightChild(currentIndex), branch.right);
    } 
    //NOTE: This will delete the WHOLE branch with index wantIndex, all sub-branches also
    //This is private! To remove last users should use  removeLast()  instead
    //Note, this takes NOT care of m_size, so should ONLY be used by removeLast()
    private T removeBranch(int wantIndex, int currentIndex, Node<T> branch) { //branch cannot be a leaf
        int leftIndex = leftChild(currentIndex);
        if (leftIndex == wantIndex) {
            T temp = branch.left.value;
            branch.left = null;    //m_size have to be decremented
            return temp;
        }
        int rightIndex = rightChild(currentIndex);
        if (rightIndex == wantIndex) {
            T temp = branch.right.value;
            branch.right = null;  //m_size have to be decremented
            return temp;
        }
        if (leftLeadsToIndex(wantIndex, currentIndex)) return removeBranch(wantIndex, leftIndex, branch.left);
        return removeBranch(wantIndex, rightIndex, branch.right);
    } 
    
    private boolean leftLeadsToIndex(int wantIndex, int currentIndex) {
        int depthRemain = depth(wantIndex) - depth(currentIndex); //So NOT included this depth
        int left = leftChild(currentIndex);
        return (maxIndexInDepth(depthRemain, left) >= wantIndex);        
    }
            
}